struct dsu_on_tree_t{

using llt = long long;

// 点权值类型
using node_weight_type = llt; 
// 答案类型
using answer_type = llt;
// 树相关
using vi = vector<int>;

int N;
vector<vi> G; // 树, 1-base

// 树链剖分结构
struct node_t{
    int size; // 子树尺寸
    int hson; // 重儿子，原树编号
    int nid;  // 树链中的新编号 
    int mdes; // 本子树全部在[nid, mdes]之间
};
// 树链
vector<node_t> Nodes;
// 新旧编号映射
vi New2Old; // 剖分编号为i，则New2Old[i]是原树编号，显然有 i == Nodes[New2Old[i]].nid

int Root;
int TimeStamp;

vi Depth;
vector<node_weight_type> W; // 点权值

vector<answer_type> Ans;

// 初始化
void init(int n){
    G.assign((N = n) + 1, {});
    Nodes.assign(N + 1, {0, 0, 0, 0});
    New2Old.assign(N + 1, TimeStamp = 0);
    Depth.assign(N + 1, 0);
    W.assign(N + 1, {});

    return;
}

// 建边
void mkDiEdge(int a, int b){
    G[a].push_back(b);
}
void mkBiEdge(int a, int b){
    mkDiEdge(a, b);
    mkDiEdge(b, a);
}

// 递归重儿子
void _dfsHeavy(int u, int p){
    Depth[u] = Depth[p] + 1;
    auto & n = Nodes[u];
    n.size = 1;
    New2Old[n.nid = ++TimeStamp] = u;

    for(auto v : G[u]){
        if(v == p) continue;
        _dfsHeavy(v, u);
        n.size += Nodes[v].size;
        if(Nodes[n.hson].size < Nodes[v].size) n.hson = v;
    }

    n.mdes = TimeStamp;
    return;
}
// 递归求解过程
void _dfs(int u, int p, bool keep){
    const auto & n = Nodes[u];
    for(auto v : G[u]){
        if(v == p or v == n.hson) continue;
        _dfs(v, u, false);
    }
    // 最后递归重儿子
    if(n.hson) _dfs(n.hson, u, true);

    // 统计，此时重儿子的答案已在数据结构中
    if(n.hson){ // 暴力统计轻儿子 
        // u子树的所有节点在树链中的编号就是该区间
        for(int i=n.nid,h=Nodes[n.hson].nid;i<=n.mdes;++i){
            if(i == h) continue;
            _count(u, New2Old[i]); // 统计节点对答案的贡献
        }
    }else{ // 该节点是叶子，统计u本身即可
        _count(u, u);
    }

    // 回答跟u有关的问题
    _answer(u);

    // 清空跟u有关的保存答案的数据
    if(not keep){
        _clean(u);
    }
    return;
}
// 对外
void solve(int root){
    _dfsHeavy(Root = root, 0);
    _dfs(Root, 0, true);
    return;   
}

// 实现以下三个功能即可
// 统计节点u对rt子树答案的贡献
void _count(int rt, int u){
    assert(0);
}

// 回答跟rt子树有关的问题
void _answer(int rt){
    assert(0);
}

// 清空rt子树保存的答案
void _clean(int rt){
    assert(0);
}

};